package gold.digger;

import gold.utils.InputUtil;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC486 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        Map<String, Boolean> memo = new HashMap<>();

        public boolean PredictTheWinner(int[] nums) {
            return dfs(nums, 0, nums.length - 1, true, 0, 0);
        }

        public boolean dfs(int[] nums, int start, int end, boolean curYouShouldChoose, int yourCount, int hisCount) {
            if (start > end) return yourCount >= hisCount;
            String key = start + "_" + end;
//            if (memo.containsKey(key)) return memo.get(key);

            boolean chooseStart, chooseEnd, finalResult;
            if (curYouShouldChoose) {
                chooseStart = dfs(nums, start + 1, end, !curYouShouldChoose, yourCount + nums[start], hisCount);
                chooseEnd = dfs(nums, start, end - 1, !curYouShouldChoose, yourCount + nums[end], hisCount);
                finalResult = chooseStart || chooseEnd;
            } else {
                chooseStart = dfs(nums, start + 1, end, !curYouShouldChoose, yourCount, hisCount + nums[start]);
                chooseEnd = dfs(nums, start, end - 1, !curYouShouldChoose, yourCount, hisCount + nums[end]);
                finalResult = chooseStart && chooseEnd;
            }

            memo.put(key, finalResult);
            return finalResult;
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[] arr = InputUtil.toIntegerArray("[1,2,99]");
        System.out.println(solution.PredictTheWinner(arr));
    }

    public static void main(String[] args) throws Exception {
        LC486 an = new LC486();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
